package com.zklh.leetcode.array.middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * N皇后解法
 * 这里使用回溯算法, 暴力破解, 算法思路和普通回溯一致, 定义一个可供选择的棋盘, 提供一个路径, 选择顺序 从一维开始, 一个索引选择一个节点
 * 遍历当前所有可选节点 当选择一个节点作为皇后节点, 更新棋盘中该节点的状态, 以及将其纵向横向斜线上所有节点的占用次数 + 1,
 * 向下调用
 * 调用完成 撤销选择, 继续其他选择
 * @author 坐看落花
 * @version 1.0
 * @date 2021/8/8 15:29
 */
public class Solution51 {

    private List<List<String>> result = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        // 定义棋盘, 存储被历史皇后占有次数, > 0 就说明被占用了
        int[][] map = new int[n][n];
        List<Integer> trace = new ArrayList<>(n);
        backtracking(map, trace);
        return result;
    }

    private void backtracking(int[][] map, List<Integer> trace) {
        if (trace.size() == map.length) {
            // 将trace 存入结果, 这里需要将trace 转化为结果
            result.add(convert(trace, map[trace.size()-1].length));
            return;
        }
        int floor = trace.size();
        int[] options = map[floor];
        for (int i = 0; i < options.length; i++) {
            // 如果已经被其他皇后占用了
            if (options[i] > 0) {
                continue;
            }
            // 选择一个节点, 将其横向 纵向 斜向占用
            trace.add(i);
            select(map, floor, i);
            // 继续向下调用
            backtracking(map, trace);
            // 撤销选择, 撤销占用
            trace.remove(floor);
            unselect(map, floor, i);
        }
    }

    private void select(int[][] map, int floor, int i) {
        select(map, floor, i, 1);
    }



    private void unselect(int[][] map, int floor, int i) {
        select(map, floor, i, -1);
    }

    /** 指定方向进行选择, 如果direction 是 -1 则就是反向选择了, 就是取消选择了
     * @param map
     * @param floor
     * @param i
     * @param direction
     */
    private void select(int[][] map, int floor, int i, int direction) {
        // 横向选择
        for (int i1 = 0; i1 < map[floor].length; i1++) {
            map[floor][i1] += direction;
        }

        // 纵向 选择
        for (int i1 = 0; i1 < map.length; i1++) {
            map[i1][i] += direction;
        }

        // floor, i 在上述过程中多加了一次, 减回去
        map[floor][i] -= direction;

        int x, y;
        /* 升序斜向 选择 */
        // 升序向上
        x = floor; y = i;
        while (--x >= 0 && ++y < map[floor].length) {
            map[x][y] += direction;
        }
        // 升序向下
        x = floor; y = i;
        while (++x < map.length && --y >= 0) {
            map[x][y] += direction;
        }

        /* 降序斜向 选择 */
        // 降序向上
        x = floor; y = i;
        while (--x >= 0 && --y >= 0) {
            map[x][y] += direction;
        }
        // 降序向下
        x = floor; y = i;
        while (++x < map.length && ++y < map[floor].length) {
            map[x][y] += direction;
        }
    }

    private List<String> convert(List<Integer> trace, int width) {
        StringBuilder sb = new StringBuilder();
        List<String> traceStrList = new ArrayList<>();
        for (int floor = 0; floor < trace.size(); floor++) {
            // 清空
            sb.delete(0, sb.length());
            // 当前选中位置 就是 floor, i 该节点为Q 其他节点为.
            int i = trace.get(floor);
            int start = 0;
            for (; start < i; start++) {
                sb.append(".");
            }
            sb.append("Q");
            for (i++; i < width; i++) {
                sb.append(".");
            }
            traceStrList.add(sb.toString());
        }
        return traceStrList;
    }

    public static void main(String[] args) {
        Solution51 solution51 = new Solution51();
        System.out.println(solution51.convert(Arrays.asList(3, 2, 0 ,1), 4));

        int[][] map = new int[4][4];

        solution51.select(map, 1, 1);
        solution51.unselect(map, 1, 1);

        System.out.println(solution51.solveNQueens(4));
    }

}
